graph = {
    "A" : ['B', "C"],
    "B" : ["A", 'C', "D"],
    "C" : ["A", 'B', "D", "E"],
    "D" : ["B", 'C', "E", "F"],
    "E" : ["C", "D"],
    "F" : ["D"]
}

def BFS(graph, s):
    queue = []
    queue.append(s)
    # 看已经走过哪些节点
    seen = set()
    seen.add(s)
    while(len(queue) > 0):
        vertex = queue.pop(0)#pop(0)表示把第一个数取出来
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
        print(vertex)

BFS(graph, "A")
print('----------')
BFS(graph, "E")

print('==========')
#使BFS输出树状结果，需使用parent映射
graph = {
    "A" : ['B', "C"],
    "B" : ["A", 'C', "D"],
    "C" : ["A", 'B', "D", "E"],
    "D" : ["B", 'C', "E", "F"],
    "E" : ["C", "D"],
    "F" : ["D"]
}

def BFS(graph, s):
    queue = []
    queue.append(s)
    seen = set()
    seen.add(s)
    parent = {s : None}

    while(len(queue) > 0):
        vertex = queue.pop(0)#pop(0)表示把第一个数取出来
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
                parent[w] = vertex
        print(vertex)
    return parent

parent = BFS(graph, "E")
print(parent)#该方式运行代码后显示的结果较乱，下面则显示为（当前点，前一点）
print('----------')
for key in parent:
    print(key, parent[key])
print('----------')#显示从E点到B点的最短路径
v = 'B'
while v != None:
    print(v)
    v = parent[v]

